Short for “discrete cosine transform,” a DCT is a technique for representing waveform data as a weighted sum of cosines, and is commonly used for image compression. Closely related to the discrete Fourier transform (“DFT”), discrete cosine transformations involve manipulation of real numbers only, offering energy compaction improvements over DFT by eliminating artificial discontinuities that appear in DFTs.
Similarly, discrete wavelet transforms (“DWT”) are designed to decorrelate an image, decomposing an image block into several subbands, and transforming an image data signal into two or more decimated signals corresponding to different frequency bands. The subbands consist of coefficients that describe the horizontal and vertical spatial frequency characteristics of the original tile component. The DWT generally results in the signal energy being concentrated in a small number of subbands, and the subbands subsequently tend to compress more easily than the original image.
Attributed to these and other appealing qualities, DCTs and DWTs are popularly deployed in a broad class of decoding techniques, known as transform coding or block quantization, which attempt to reduce image signal redundancy by representing signals with a new set of orthogonal bases, reducing the spatial correlations that occur between adjacent pixels. Using DCTs and DWTs, merely a fraction of the transform coefficients are encoded, with tolerable deterioration in image fidelity. JPEG and JPEG 2000 are examples of well known image compression mechanisms which utilize DCT and DWT, respectively.
One problem common to conventional DCT and DWT-based image compression algorithms relates to the wide disparity in color composition found in large images, such as images measuring 2048 pixels ×2048 pixels or larger. Widely disparate color compositions thwart DCT and DWT algorithms, which are most effective when color statistics of encoded blocks are similar. In order to reduce color composition disparity in large images, the conventional image compression algorithms partition an image into fixed blocks of N×N pixels, where N is either arbitrary, or based upon predetermined simulation results of other natural images.
The choice of block sizes is crucial, since the selection of too large of a block can include more than one region with different frequency properties, while the selection of too small of a block results in less efficient image compression. As such, it is a disadvantage of the conventional image compression mechanisms to choose block sizes which are not tailored to the individual images being compressed, and which do not compensate for regions of similar frequency properties. By ignoring these similar regions, conventional image compression mechanisms suffer from increased loss of coefficient magnitudes, decreased overall compression efficiency and increased time required to transmit compressed images.
It is therefore considered highly desirable to provide an enhanced mechanism for compressing images which groups regions or blocks of data with similar frequency properties, in order to increase compression efficiency. In particular, it is desirable to have an iterative region-growing algorithm for partitioned images, which grows regions based on the similarity or difference of color characteristics of non-overlapping regions of the image, resulting in more efficient block coding.